/*
 * EditDistance.cpp
 *	Edit distance问题
 *	算法导论习题15-3，是个比较有代表性的题。
 *  Created on: 2012-5-19
 *      Author: xubin
 */
/*
 * 分析：http://nosql-wiki.org/foswiki/bin/view/Main/IntroductionToAlgorithmChapter15#15_3 (这篇文章里有一个错误，就是交换操作时，是后退到(i-2,j-2)，而非(i-1,j-1)
 * 用了好几个for 循环，是为了处理[0, 0....N] [0....N, 0] [1,1....N], [1......N, 1] 这么几种特殊情况
 * 把这几种特殊情况放到一个完整的 0->N的二重循环里也可以，但那样的话，For循环里还有很复杂的if-else判断，把我自己都搞晕了。
 * 所以就拿出来先处理。不过这样很占代码行。
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAX_INT	( 0x7fffffff  - 100)
class EditDistance {
private:
	string src;
	string dst;
	static const unsigned cost_copy = 1;
	static const unsigned cost_replace = cost_copy;
	static const unsigned cost_delete = cost_copy;
	static const unsigned cost_insert = cost_copy;
	static const unsigned cost_twiddle = cost_copy; //交换两字符
	static const unsigned cost_kill = cost_copy;

#define min_ONe(a,b)	((a)<(b) ?  (a) : b)
	int min(int a = MAX_INT, int b = MAX_INT, int c = MAX_INT, int d = MAX_INT,
			int e = MAX_INT) {
		int m = min_ONe(a, b);
		m = min_ONe(m, c);
		m = min_ONe(m, d);
		m = min_ONe(m, e);
		return m;
	}

	void debug(vector<vector<int> > &v) {
		for (int i = 0; i < src.size(); i++) {
			for (int j = 0; j < dst.size(); j++) {
				cout << v[i][j] << ", ";
			}
			cout << endl;
		}
	}

public:
	EditDistance(string src, string dst) {
		this->src = src;
		this->dst = dst;
	}

	void solve() //返回最小Edit distance
	{
		vector<vector<int> > opt(src.size(), vector<int>(dst.size()));
		int i = 0, j = 0;
		for (j = 0; j < dst.size(); j++) {
			int i = 0;
			int cc = MAX_INT;
			int cr = MAX_INT;
			int cd = MAX_INT;
			int ci = MAX_INT;
			int ct = MAX_INT;
			int ck = MAX_INT;
			if (src[i] == dst[j]) {
				cc = j * cost_insert + cost_copy;
			} else {
				cr = j * cost_insert + cost_replace;
				ci = j * cost_insert + cost_insert;
			}
			int cost = min(cc, cr, ci);
			if (j == dst.size() - 1) {
				if (i != src.size() - 1) {
					cost += cost_kill;
				}
			}
			opt[i][j] = cost;
		}

		for (i = 0; i < src.size(); i++) {
			int j = 0;
			int cc = MAX_INT;
			int cr = MAX_INT;
			int cd = MAX_INT;
			int ci = MAX_INT;
			int ct = MAX_INT;
			int ck = MAX_INT;
			if (src[i] == dst[j]) {
				cc = i * cost_delete + cost_copy;
			} else {
				cr = i * cost_delete + cost_replace;
				ci = i * cost_delete + cost_insert;
			}
			int cost = min(cc, cr, ci);
			if (j == dst.size() - 1) {
				if (i != src.size() - 1) {
					cost += cost_kill;
				}
			}
			opt[i][j] = cost;
		}

		for (j = 1; j < dst.size(); j++) {
			int i = 1;
			int cc = MAX_INT;
			int cr = MAX_INT;
			int cd = MAX_INT;
			int ci = MAX_INT;
			int ct = MAX_INT;
			int ck = MAX_INT;
			if (src[i] == dst[j]) {
				cc = opt[i - 1][j - 1] + cost_copy;
			} else {
				cr = opt[i - 1][j - 1] + cost_replace;
				ci = opt[i][j - 1] + cost_insert;
				cd = opt[i - 1][j] + cost_delete;
			}
			if (src[i] == dst[j - 1] && src[i - 1] == dst[j]) {
				ct = (j - 1) * cost_insert + cost_twiddle;
			}
			int cost = min(cc, cr, ci, cd, ct);
			if (j == dst.size() - 1) {
				if (i != src.size() - 1) {
					cost += cost_kill;
				}
			}
			opt[i][j] = cost;
		}

		for (i = 1; i < src.size(); i++) {
			int j = 1;
			int cc = MAX_INT;
			int cr = MAX_INT;
			int cd = MAX_INT;
			int ci = MAX_INT;
			int ct = MAX_INT;
			int ck = MAX_INT;
			if (src[i] == dst[j]) {
				cc = opt[i - 1][j - 1] + cost_copy;
			} else {
				cr = opt[i - 1][j - 1] + cost_replace;
				ci = opt[i][j - 1] + cost_insert;
				cd = opt[i - 1][j] + cost_delete;
			}
			if (src[i] == dst[j - 1] && src[i - 1] == dst[j]) {
				ct = (i - 1) * cost_delete + cost_twiddle;
			}
			int cost = min(cc, cr, ci, cd, ct);
			if (j == dst.size() - 1) {
				if (i != src.size() - 1) {
					cost += cost_kill;
				}
			}
			opt[i][j] = cost;
		}

		for (i = 2; i < src.size(); i++) {
			for (j = 2; j < dst.size(); j++) {
				int cc = MAX_INT;
				int cr = MAX_INT;
				int cd = MAX_INT;
				int ci = MAX_INT;
				int ct = MAX_INT;
				int ck = MAX_INT;
				if (src[i] == dst[j]) {
					cc = opt[i - 1][j - 1] + cost_copy;
				} else {
					cr = opt[i - 1][j - 1] + cost_replace;
					ci = opt[i][j - 1] + cost_insert;
					cd = opt[i - 1][j] + cost_delete;
				}
				if (src[i] == dst[j - 1] && src[i - 1] == dst[j]) {
					ct = opt[i - 2][j - 2] + cost_twiddle;
				}
				int cost = min(cc, cr, ci, cd, ct);
				if (j == dst.size() - 1) {
					if (i != src.size() - 1) {
						cost += cost_kill;
					}
				}
				opt[i][j] = cost;
			}
		}
		debug(opt);
		int minSteps = MAX_INT;
		j = dst.size()  -1;
		for (i = 0; i < src.size(); i++) {
			if (opt[i][j] < minSteps)
				minSteps = opt[i][j];
		}
		cout<<minSteps<<endl;
	}
};

int main() {
	EditDistance e(string("aaleg"), string("hel"));
	e.solve();
}

